/**
* @description: LeetCode 400
* @author hewei
* @date 2022/7/21 16:26
* @version 1.0
*/

public class FindNthDigit {

    public static void main(String[] args) {
        FindNthDigit findNthDigit = new FindNthDigit();
        System.out.println(findNthDigit.findNthDigit(1000000000));
    }

    public int findNthDigit(int n) {
        long sum = 0;
        long temp = 0;
        int i = 0;

        //sum只是一个中间变量，重点是temp记录了没超过目标位数时，之前位数的所有数的位数之和
        while (sum < n) {
            temp = sum;
            sum += (long) ((i + 1) * Math.pow(10, i) * 9);
            ++i;
        }

        //总的位数和减去小于目标位数的和，得到的是目标位数从开始到目标数的位数之和
        n -= temp;

        //获得答案所在的地方在目标数的第几个位置
        int count = n % i;

        //找到上一个位数的位后一个数是多少，9999.....
        int temp2 = 0;
        for (int k = 0; k < i - 1; k++) {
            temp2 = temp2 * 10 + 9;
        }

        //最后一个数加上目标数前面的数的个数
        temp2 += n / i;

        //如果为零就代表是上一个位置的最后一位数
        if (count == 0) return temp2 % 10;
        String ans = temp2 + 1 + "";
        return ans.charAt(count - 1) - '0';
    }
}
